A switching network is comprised of ports, pins, conductors and switches. The ports and pins are external constructs of the switching network where each port contains a plurality of pins to interface to other switching networks or circuits. The conductors and switches are internal constructs of the switching network configured to transfer data or signals from pins of a first plurality of ports of a first type to pins of a second plurality of ports of a second type inside the switching network. The pins of the first plurality of ports receive data or signals and transmit those data or signals through the conductors and the switches of the switching network to the pins of the second plurality of ports. The pins of the ports of the switching network are physically connected to respective conductors of the switching network. The switches of the switching network are program controlled to enable connection paths among the pins of the first plurality of ports to the pins of the second plurality of ports. The connection paths connecting two pins inside the switching network can sometimes involve one or more intermediate conductors coupled through switches of the switching network. Thus the pins and ports of the switching network are external constructs where the pins of ports of the first type receives data or signals from sources such as other switching networks and circuits and the pins of ports of the second type transmit signals or data to destinations such as other switching networks and circuits. The switches and conductors of the switching network are internal constructs where the data or signals on the pins of ports of the first types are transmitted to the pins of ports of the second type through the switches and conductors of the switching network.
Generally, the transmission of data or signals from the first plurality of ports to the second plurality of ports through the switching network is substantially simultaneous and non-blocking. In the case where data or signals of a single pin of a port of the first plurality of ports are transmitted to multiple pins of respective multiple ports of the second plurality of ports, this is called multicasting in network connection terms. The switching network can also be used as programmable interconnect circuitry for programmable logic circuits. In the case of programmable logic circuits, the multicasting corresponds to a source (output) connecting to multiple inputs. Each of the pins of the switching network connects to a conductor internally inside the switching network. For ease of illustration and consistency with the conventional way to describe such technologies, we shall denote each switching network under discussion as having a first set of M conductors (having m number of conductors, for example) to correspond to the pins of the first plurality of ports of the switching network. We denote the second plurality of ports as having k ports where each of the k ports has ni pins with i=[1−k] where each ni is at most equal to n. Additionally, we denote a k plurality of conductors where each of the k plurality of conductors having Ni[1−ni] conductors for i=[1−k]. Thus the switching network can be used to connect the pins of the first plurality of ports to the pins of the k ports through use and control of switches and conductors. Each of the pins of the first plurality of ports is capable of connecting to at least one pin to each of the k ports through the switching network. Typically, multiple numbers of pins of the first plurality of ports can independently connect to the pins of the k ports using the switching network without blocking.
A well-known switching network is the full matrix switch. FIG. 1 illustrates a prior art embodiment of a full matrix switching network 10 with one port 110 having m number of pins which are connected to the m number of M conductors M[1−m] 11 inside the switching network 10. The conductors 111-114 of 11 are in term coupled to the pins of each of the k ports 12-14 through the switches 15 and the Ni[1−ni] conductors 120-140 of the network 10 for i=[1−k]. Each of the k ports 12-14 has ni pins with i=[1−k] (e.g. port 12 has n1 pins, port 13 has n2 pins, port 14 has nk pins). Total number of switches in the full matrix switching network 10 is m×sumi=[1−k]ni switches; as an example, for m=28, each ni=4 and k=9, the number of switches is 1,008. Any subset of the M conductors 11 in FIG. 1 can connect to a pin in each of the k ports 12-14 through the switches 15 of the full matrix switching network without blocking.
FIG. 2 illustrates a prior art embodiment of a 1-SN switching network 20 by Pani et. al. (U.S. patent application Ser. No. 10/814,943, filed Mar. 30, 2004) with port 221 having m=28 pins and the same M conductors M[1−m] 21 connecting to the pins of port 221. Each of the k ports 222-230 have four pins which are connected to the respective Ni[1-4] conductors 22-30 of the switching network 20 where k=9, with each Ni=4 for i=[1−k], in FIG. 2. The number of switches in 31 of FIG. 2 is 28×(4+9)=364. 31 of FIG. 2 represent the switches connecting between the intersecting conductors (32 to 22-30). Similarly, as in the full matrix of FIG. 1, the 1-SN of FIG. 2 can connect any subset of the m pins of port 221 through connection to the respective M conductors 21 to a pin in each of the k ports 22-30 through the switches 31 an the intermediate conductors 32 and the Ni[1−ni] conductors 222-230 of the 1-SN; 32 are intermediate conductors which serve to connect the M conductors 21 to the k ports of n pins 222-230 through 22-30 using switches 31 of the 1-SN 20.
The difference between the full matrix switch of FIG. 1 and the 1-SN of FIG. 2 inside the respective network is that each M conductor 21 connects to the conductors of the k plurality of conductors 22-30 through one of the intermediate I[1-28] conductors 32 while there is no intermediate conductor in the full matrix switch. The number of switches required in the full matrix switch and the 1-SN is M×k×n and at most M×(k+n), respectively. The number of switches in the prior art switching network of FIG. 1 can be significantly larger than that of FIG. 2 when the size of M, ni and k becomes large. As an example, for M=256, ni=16, and k=18, the full matrix switching network of FIG. 1 would have 256×(16×18)=73,728 switches while a 1-SN switching network of FIG. 2 would be 256×(16+18)=8,704 switches and one 2-SN switching network embodiment of prior art by Pani et. al. (U.S. patent application Ser. No. 10/814,943, filed Mar. 30, 2004) would be 256×(4+4+18)=6,656 switches.
When the size of a switching or interconnect network becomes real large (i.e. the M conductors and the Ni[1−n] conductors of the k plurality of conductors are in the thousands or more), the number of switches required to effect interconnect from M conductors to the Ni[1−n] conductors in either FIG. 1 or FIG. 2 scheme will become impractical. Instead, a hierarchical scheme can be used to interconnect switching networks to effect large number of M conductors to the Ni[1−n] conductors. It is worth noting that, it makes sense to describe connection inside the switching network as connecting the M conductors to the k plurality of conductors Ni[1−ni] for i=[1−k] while viewed externally, the connections are from the pins of the first plurality of ports (in FIG. 1 and FIG. 2, there is one such port, 110 and 221, respectively) to the pins of the k ports (which are the second plurality of ports).
Another type of switching network is the Clos network described by L. M. Spandorfer in 1965 where any pin of the N nodes is connectable to any other pin of the N nodes through the Clos network independently without blocking. Reblewski et. al. in U.S. Pat. No. 6,594,810 described a scalable architecture using crossbars for a reconfigurable integrated circuit. Wong in U.S. Pat. No. 6,693,456 described an architecture using Benes networks for field programmable gate array. A switching network (SN) was disclosed by the present inventors in U.S. patent application Ser. No. 10/814,943, filed Mar. 30, 2004. In one embodiment of the SN, the M conductors are connected to the k plurality of conductors in the SN through at least one intermediate stage of interconnection, in addition to switches in the SN; any conductor of the M conductors can connect to a Ni[1−n] conductor in each of the k ports independently in the SN.
When the number of the M conductors and the k plurality of conductors are large, it becomes impractical to use one large switching network to make all the programmable interconnections; instead, hierarchy of switching networks are generally used to reduce the total number of switches required in the resulting interconnect system. Additionally, hierarchy is used to take into account the varying amount of traffic amongst large number of traffic origination and termination nodes throughout different locations in the overall network. Using telephone network as an example, local residential and business traffic in a small geographic location are bundled into a central office so the central offices serve as the lowest level of switching networks. The voice and data traffic from the central offices are in turn bundled into regional offices which serve as the next higher level of switching networks and the regional offices are then interconnected to yet higher level of switching networks. Each of the different levels of switching networks has varying size and capacity to handle data and voice traffic in the overall network. One of the common problems to be solved in a hierarchical switching networks is thus to size the overall hierarchy of switching networks to handle the varying amounts of local, intermediate, and higher levels of data and signals transmitted and received by the different switching networks and limit the total number of switches required to allow effective connections for very large number of M conductors to large number of k plurality of conductors while substantially preserving the non-blocking property of the interconnection fabric.